package swardToOffer.struct_1_arr;

/**
 * @Author ChanZany
 * @Date 2021/5/19 16:26
 * @Version 1.0
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排列，每一列都按照从上到下递增的顺序排列
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
 * case:
 * 1,2,8,9
 * 2,4,9,12
 * 4,7,10,13
 * 6,8,11,15
 * 输入7返回true，输入5返回false
 * 思路：
 * 从矩阵的右上角(x)往左上角进行判断，
 * 如果matrix[x]>num,则需要查找x的左下角区域(新的matrix),否则查找x的下方区域(当前列)
 */
public class MatrixFind {
    private boolean find(int[][] matrix, int num) {
        if (matrix.length <= 0) return false;
        int row = 0;//第一行的行标
        int column = matrix[0].length -1;//最后一列的列标
        while (row<matrix.length-1 && column>0){
            if (num==matrix[row][column]){
                return true;
            }else if (num<matrix[row][column]){
                column --;
            }else {
                row ++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[5][4];
        matrix[0] = new int[]{1, 2, 8, 9};
        matrix[1] = new int[]{2, 4, 9, 12};
        matrix[2] = new int[]{4, 7, 10, 13};
        matrix[3] = new int[]{6, 8, 11, 15};
        MatrixFind matrixFind = new MatrixFind();
        System.out.println(matrixFind.find(matrix, 5));
        System.out.println(matrixFind.find(matrix, 7));
    }
}
